Many communications systems today use forward error correction (FEC) codes in order to improve data robustness in the presence of channel noise. In many systems, the FEC scheme used is the well known Reed Solomon (RS) encoding scheme. Reed Solomon codes are used in a wide variety of commercial applications, most prominently in CDs and DVDs, and in data transmission technologies such as DSL, DVB and WiMAX.
In a Reed-Solomon code, the data encoded is first visualized as a polynomial. The code relies on a theorem from linear algebra that states that any k distinct points uniquely determine a polynomial of degree at most k−1. The Reed Solomon error correction code functions by oversampling a polynomial constructed from the data. The polynomial is evaluated at several points, and these values are sent or recorded. By sampling the polynomial more often than is necessary, the polynomial is over determined. As long as a sufficient number of the points are received correctly, the receiver can recover the original polynomial even in the presence of a few erroneous points.
The standard way to decode RS codes is by using a hard decision decoder that only uses the channel output after it is transformed to bits. Using the soft channel output (i.e. before slicing), however, can significantly improve performance. Several soft decoding algorithms are known in the art, but most of them have the disadvantage of having high implementation complexity.
The Chase algorithm is a well known algorithm for approximate soft decoding of binary error control codes with a well-defined trade-off between performance and complexity. The Chase algorithm begins by identifying the p least reliable codeword symbols of a received codeword and then enumerates all 2p corresponding codewords while fixing the more reliable codewords. The Chase algorithm decodes each of the 2p codewords using a simple hard-decoding algorithm. Finally, the Chase algorithm chooses the candidate codeword that the hard decoder was able to decode.
Differential decoding is a technique used in digital communications to provide unambiguous signal reception when using some types of modulation. It makes transmitted data depend not only on the current bit (or symbol), but also on the previous one. Common types of modulation that require differential coding include phase shift keying and quadrature amplitude modulation (QAM).
To demodulate a BPSK signal, for example, a local oscillator must be made synchronous to the remote one. This is accomplished using a carrier recovery circuit. A carrier can be recovered in different ways, however, depending upon a count of valid phases (two for BPSK). For this coding, if a carrier signal is recovered incorrectly, the received data is inverted. Using differential decoding, determining what was transmitted depends only on the difference between two consecutive received symbols and not on their absolute values. Thus, regardless of whether the data stream is inverted, the decoded data will always be correct.
Differential coding applies to symbols as opposed to bits. To resolve 180 degree ambiguity, single bits used as the symbols are sufficient. When dealing with ambiguity of 90 degree, pairs of bits are used Three bits are used to resolve 45 degree ambiguity (e.g., in 8-PSK).
A system that employs a differential encoder/decoder is robust to constant phase shifts of 90 degrees, 180 degrees and 270 degrees in the QAM constellation. The differential encoder encodes the two MSBs of the constellation point, which are the bits that define the quadrant the constellation point is located in.
A problem arises, however, when the Chase algorithm is used in a system that incorporates a differential decoder. The Chase algorithm is difficult to implement in a system that employs a differential encoder/decoder. This is because the algorithm requires the QAM demodulator to output two hard decision candidates for each constellation point. The first candidate has a better probability to be the correct decision than the second candidate. If the first and second candidates are located in different quadrants, then a trellis scheme of two branches is required. Since the differential decoder has a memory of length one (i.e. one for I and one for Q), the two branches are further split into a maximum of four branches. Keeping tracking of this four branch trellis is complicated and could require significantly more memory depending on the system.
For example, consider a RS system with a 192 symbol block length. The Chase algorithm attempts to improve the soft value reliability of the three worst detected symbols. Given four trellis branches for each symbol yields 43=64 iterations. In most cases, doing this is impractical because of the computing resources, time and expense required to implement it.
It is thus desirable to have a mechanism that provides a means of differential decoding the demodulator output that overcomes the disadvantage of the prior art. It is further desirable that the different decoding mechanism perform the decoding of the demodulated symbols to generate soft value information required by FEC decoders such as those implementing Reed Solomon decoding without the large computing resources and cost required of prior art mechanisms.